package cn.yuemouren.toflashback;

import java.util.LinkedList;
import java.util.List;

/**
 * <p>
 * 全排列问题 -> 运用回溯算法
 *
 * 回溯算法时间复杂度是 n的n！
 * </p>
 *
 * @author Timi
 * @date 2021/5/11 上午9:30
 **/
public class FullPermutation {

    private List<List<Integer>> result;

    public FullPermutation() {
        result = new LinkedList<>();
    }

    /**
     * 输入数组，返回所有全排列结果
     *
     * @param nums 原始数组
     *
     * @return 全排列结果
     */
    public List<List<Integer>> fullPermutation(int[] nums) {

        LinkedList<Integer> track = new LinkedList<>();
        backtracking(nums, track);
        return result;
    }

    /**
     * 运用回溯算法解决全排列问题nums
     *
     * @param nums 原始数组
     * @param track 其中一种情况
     */
    private void backtracking(int[] nums, LinkedList<Integer> track) {
        //一次全排序结束条件
        if(nums.length == track.size()){
            result.add(new LinkedList<>(track));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            if(track.contains(num)){
                continue;
            }
            //做选择
            track.add(num);
            //首位固定，继续向下迭代
            backtracking(nums,track);
            //移除当前选择
            track.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        FullPermutation f = new FullPermutation();
        List<List<Integer>> lists = f.fullPermutation(nums);
        System.out.println(lists);
    }
}
